/* Kernel module to match a string into a packet.
 *
 * Copyright (C) 2000 Emmanuel Roger  <winfield@freegates.be>
 * 
 * ChangeLog
 *	02.05.2001: Gianni Tedesco <gianni@ecsc.co.uk>
 *		Fixed kernel panic, due to overrunning boyer moore string
 *		tables. Also slightly tweaked heuristic for deciding what
 * 		search algo to use.
 * 	27.01.2001: Gianni Tedesco <gianni@ecsc.co.uk>
 * 		Implemented Boyer Moore Sublinear search algorithm
 * 		alongside the existing linear search based on memcmp().
 * 		Also a quick check to decide which method to use on a per
 * 		packet basis.
 */

#include <linux/module.h>
#include <linux/skbuff.h>
#include <linux/tcp.h>
#include <linux/netfilter_ipv4/ip_tables.h>
#include "ipt_string.h"

#define max(a,b) (a>b?a:b)
int skip[BM_MAX_HLEN];
int shift[BM_MAX_HLEN];

#define URL_MAX_LEN 2048
char *urldecoded;

/* Boyer Moore Sublinear string search - VERY FAST */
char *search_sublinear (char *needle, char *haystack, int needle_len, int haystack_len) 
{
	int M1, right_end, sk, sh;  
	int ended, j, len[BM_MAX_HLEN];
	int i;

	/* Setup skip/shift tables */
	M1 = right_end = needle_len-1;
	for (i = 0; i < BM_MAX_HLEN; i++) skip[i] = needle_len;  
	for (i = 0; needle[i]; i++) skip[needle[i]] = M1 - i;  

	for (i = 1; i < needle_len; i++) {   
		for (j = 0; j < needle_len && needle[M1 - j] == needle[M1 - i - j]; j++);  
		len[i] = j;  
	}  

	shift[0] = 1;  
	for (i = 1; i < needle_len; i++) shift[i] = needle_len;  
	for (i = M1; i > 0; i--) shift[len[i]] = i;  
	ended = 0;  
	
	for (i = 0; i < needle_len; i++) {  
		if (len[i] == M1 - i) ended = i;  
		if (ended) shift[i] = ended;  
	}  

	/* Do the search*/  
	while (right_end < haystack_len)
	{
		for (i = 0; i < needle_len && haystack[right_end - i] == needle[M1 - i]; i++);  
		if (i == needle_len) {
			return haystack+(right_end - M1);
		}
		
		sk = skip[haystack[right_end - i]];  
		sh = shift[i];
		right_end = max(right_end - i + sk, right_end + sh);  
	}

	return NULL;
}  

/* Linear string search based on memcmp() */
char *search_linear (char *needle, char *haystack, int needle_len, int haystack_len) 
{
	char *k = haystack + (haystack_len-needle_len);
	char *t = haystack;
	
	while ( t <= k ) {
		if ( memcmp(t, needle, needle_len) == 0 ) return t;
		t++;
	}

	return NULL;
}

static int my_toupper(int what)
{
	if((what<'a')||(what>'z')) return what;
	return what-32;
}

static int my_isdigit(int what)
{
	if((what<'0')||(what>'9')) return 0;
	return 1;
}

static int my_isxdigit(int what)
{
	int i;
	if(my_isdigit(what)) return 1;
	if((what>='A')&&(what<='Z')) return 1;
	i=what-32;
	if((i>='A')&&(i<='Z')) return 1;
	return 0;
}

static int nibble(char what)
{
	if (my_isdigit((int)what)) return what - '0';
	if (my_isxdigit((int)what)) return my_toupper((int)what) - 'A' + 10;
	return -1;
}

static int
match(const struct sk_buff *skb,
      const struct net_device *in,
      const struct net_device *out,
      const void *matchinfo,
      int offset,
      const void *hdr,
      u_int16_t datalen,
      int *hotdrop)
{
	const struct ipt_string_info *info = matchinfo;
	struct iphdr *ip = skb->nh.iph;
	struct tcphdr *tcp;
	int hlen,nlen;
	int head,tail;
	unsigned int tcplen;
	char *needle, *haystack, *index, *end, *url;
	proc_ipt_search search=search_linear;

	if ( !ip ) return 0;
	if (ip->protocol != 6) return 0;
	tcplen=datalen-ip->ihl*4;
        tcp = (struct tcphdr *)((char *)ip + ip->ihl*4);
	if (tcplen < sizeof(struct tcphdr) || tcplen < tcp->doff*4)return 0;
	/* get lenghts, and validate them */
	tail=info->string[0]-1;
	hlen=tcplen-tcp->doff*4;
	
	if ( tail +4 > hlen) return 0;
	haystack=(char *)ip+ip->ihl*4+tcp->doff*4;//TCP HEADER
	if(!memcmp(haystack,"GET ",4)){
		haystack=haystack+4;
		hlen=hlen-4;
	}
	else if(!memcmp(haystack,"POST ",5)){
		haystack=haystack+5;
		hlen=hlen-5;
	}
	else return 0;
	for(head=0;head<hlen&&haystack[head]!=' '&&haystack[head]!='\n';head++);
	hlen=head;

	//for(head=0;head<hlen;head++)printk("%c",haystack[head]);
	//printk("\n--------------------\n");
	
	// Decode url
	memcpy(urldecoded,haystack,hlen);
	//urldecoded[hlen]=0;
	haystack=urldecoded;

            index = (char *) haystack;
            url = (char *) haystack;
            end = (char *) haystack + hlen;

            /* walk thru each char in the payload */
            while (index < end)
            {
                /* if it's potentially "escaped" and not too close to the end of 
                   the payload */
                if ((*index == '%') && (index < end - 2))
                {
                    /* and if the following two chars are hex digits */
                    if (my_isxdigit((int)*(index+1)) && my_isxdigit((int)*(index+2)))
                    {
                        /*convert it and stuff it */
                        *url = my_toupper((nibble(*(index+1)) << 4) | nibble(*(index+2)));
                        index += 3; 
                        url++;
                        hlen -= 2;
                    }
                    else
                    {
                        *url = my_toupper(*index);
                        url++;
                        index++;
                    }        
                }
                else
                {
                    *url = my_toupper(*index);
                    url++;
                    index++;
                }
            }

	//urldecoded[hlen]=0;
	*url=0;
	//printk("%d %d %s\n--------------------\n",info->match,hlen,haystack);
	

	head=0;
	while((tail=info->string[head])){
		needle=(char *)&(info->string[head+1]);
		nlen=tail-head-1;
		head=tail;
		//printk("%d %d %d %d",nlen,hlen,head,tail);
		//
		//printk("Needle[%d]:",nlen);
		//for(k=0;k<nlen;k++)printk("%c",needle[k]);
		//printk("\n--------------------\n");
	
		//search=search_linear;
		if(info->match==1) // match include
		{
			/* The sublinear search comes in to its own
		 	* on the larger packets */
			if ( (hlen>IPT_STRING_HAYSTACK_THRESH) &&
		  		(nlen>IPT_STRING_NEEDLE_THRESH) ) {
				if ( hlen < BM_MAX_HLEN ) {
					search=search_sublinear;
				}else{
				//	if (net_ratelimit())
				//		printk(KERN_INFO "ipt_string: Packet too big "
				//		"to attempt sublinear string search "
				//		"(%d bytes)\n", hlen );
				}
			}
	    		if (search(needle, haystack, nlen, hlen)!=NULL) return 1;
		}
		else if(info->match==0) // match begin
		{
			if (memcmp(needle, haystack, nlen) == 0 ) return 1;
		}
		else if(info->match==2) // match end
		{
	    		if (memcmp(needle, haystack+hlen-nlen, nlen)==0) return 1;
		}
	}
	return 0;
}

static int
checkentry(const char *tablename,
           const struct ipt_ip *ip,
           void *matchinfo,
           unsigned int matchsize,
           unsigned int hook_mask)
{

       if (matchsize != IPT_ALIGN(sizeof(struct ipt_string_info)))
               return 0;

       return 1;
}

static struct ipt_match string_match
= { { NULL, NULL }, "string", &match, &checkentry, NULL, THIS_MODULE };

static int __init init(void)
{
	int ret;
	urldecoded=kmalloc(URL_MAX_LEN, GFP_KERNEL);
	if(!urldecoded)
		return -ENOMEM;
	ret=ipt_register_match(&string_match);
	if(ret<0)
		kfree(urldecoded);
	return ret;
}

static void __exit fini(void)
{
	ipt_unregister_match(&string_match);
	kfree(urldecoded);
}

module_init(init);
module_exit(fini);
